/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    ////// 题目没有说明树是完全二叉树，所以树的左边和右边可能为空
    int Is_sumNumbers(TreeNode *root, int val)
    {
        val = val * 10 + root->val;
        // cout << val <<endl;
        if (root->left == nullptr && root->right == nullptr)
            return val;
        int ret = 0;
        // 左子树可能为空，为空再次进入循环，那么root->val不存在，那么上面val = val*10 + root->val报错
        if (root->left)
            ret += Is_sumNumbers(root->left, val);
        // 右子树可能为空，为空再次进入循环，那么root->val不存在，那么上面val = val*10 + root->val报错
        if (root->right)
            ret += Is_sumNumbers(root->right, val);
        // 所以需要先判断左右子树是不是存在的，存在然后用一个ret来记录
        return ret;
    }
    int sumNumbers(TreeNode *root)
    {
        return Is_sumNumbers(root, 0);
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    TreeNode *pruneTree(TreeNode *root)
    {
        // 走到叶子节点的左边和右边，也就是nullptr了，返回nullptr
        if (root == nullptr)
            return nullptr;
        // 处理左边，看看我的左子树返回什么节点，然后我连接上去
        root->left = pruneTree(root->left);
        // 处理右边，看看我的右子树返回什么节点，然后我连接上去
        root->right = pruneTree(root->right);
        // 如果我这个节点的值为0，并且左右子树全为空，那么就返回空节点
        if (root->left == nullptr && root->right == nullptr && root->val == 0)
            return nullptr;
        // 如果我的左右子树有一边有值，或者说节点val为1，表示不能剪枝，返回我这个节点就行
        else
            return root;
    }
};
// 判断是不是二叉搜索树
class Solution
{
public:
    long prev = LONG_MIN;
    bool isValidBST(TreeNode *root)
    {
        if (root == nullptr)
            return true;
        auto left = isValidBST(root->left);

        {
            // 我左边进行判断，不是二叉搜索树了，我还判断右边干什么
            if (left == false)
                return false; // 剪枝
        }

        int cur = false; // cur来判断是不是二叉搜索树
        if (root->val > prev)
            cur = true;

        {
            // 我当前节点进行判断，结果我的当前节点值小于左边节点，不是二叉搜索树了，我还判断右边干什么
            if (cur == false)
                return false; // 剪枝
        }

        prev = root->val;
        auto right = isValidBST(root->right);
        return left && right && cur; // 左子树，右子树，和当前位置cur都是二叉搜索树
    }
};
//  二叉树所有路径插入字符串数组
class Solution
{
public:
    vector<string> ret;
    // string path; 本题全局的path进行回溯的话，比较麻烦，一直要pop箭头->后的数据
    // 函数头使用path，这样每次递归都创建一个局部变量path，互不干扰，帮助我们自动恢复现场
    void dfs(TreeNode *root, string path)
    {
        // if( root== nullptr)
        //     return ;
        // 叶子节点特殊处理一下，后面不带->
        // 我们只在到了叶子结点才进行push_back插入，这也就是插入了一条完整字符串
        if (root->left == nullptr && root->right == nullptr)
        {
            path += to_string(root->val);
            ret.push_back(path);
            return;
        }
        path += to_string(root->val) + "->";
        // 两个if判断就是剪枝，如果我左为空，或者右为空，我就直接不进去了，就不存在上面的递归出口了
        if (root->left)
        {
            dfs(root->left, path);
        }
        if (root->right)
        {
            dfs(root->right, path);
        }
    }
    vector<string> binaryTreePaths(TreeNode *root)
    {
        string path;
        dfs(root, path);
        return ret;
    }
};